package list;

import java.util.HashSet;
import java.util.Set;

public class LeetCode142 {
    public ListNode detectCycleSet(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (!set.add(p)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while (slow.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                while (true) {
                    if (slow == pre) {
                        return slow;
                    }
                    slow = slow.next;
                    pre = pre.next;
                }
            }
        }
        return null;
    }
}
